class Node:
    def __init__(self, key, parent):
        self.num = 1
        self.key = key
        self.left = None
        self.right = None
        self.leftNum = 0
        self.parent = parent


class Bst:
    def __init__(self):
        self.head = None

    def put(self, key):
        if self.head is None:
            self.head = Node(key, None)
            return 0
        tmp = self.head
        re = None
        while not re:
            if tmp.key == key:
                tmp.num = tmp.num + 1
                re = tmp
                break
            elif tmp.key < key:
                if tmp.right is None:
                    tmp.right = Node(key,tmp)
                    tmp.right.parent = tmp
                    re = tmp.right
                    break
                else:
                    tmp = tmp.right
            else:
                tmp.leftNum = tmp.leftNum + 1
                if tmp.left is None:
                    tmp.left = Node(key, tmp)
                    tmp.left.parent = tmp
                    re = tmp.left
                    break
                else:
                    tmp = tmp.left

        # 根据节点查找数量
        sumNum = re.leftNum
        while re:
            if re.parent is None:
                break
            parent = re.parent
            if re == parent.right:
                sumNum = sumNum + parent.num + parent.leftNum
            re = parent
        return sumNum



class Solution:
    def countSmaller(self, nums):
        if not nums:
            return []
        r = [0 for _ in range(len(nums))]
        bst = Bst()
        for i in range(len(nums) - 1, -1, -1):
            r[i] = bst.put(nums[i])

        return r


if __name__ == '__main__':
    so = Solution()
    m = [5, 2, 6, 1]
    r = so.countSmaller(m)
    print(r)
